package cn.itcast.algorithm;

import java.util.LinkedList;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;

/**
 * 一致性Hash算法 -- 带虚拟节点
 * https://blog.csdn.net/u010558660/article/details/52767218
 * create by zhangtian3 on 2019/1/7
 */
public class ConsistentHashingWithVirtualNode {
    // 待加入Hash环的服务器列表
    private static String[] servers = {"192.168.0.0:1000", "192.168.0.1:1001",
            "192.168.0.2:1002", "192.168.0.3:1003",
            "192.168.0.4:1004"} ;

    // 真实节点列表,考虑到服务器上线、下线的场景，即添加、删除的场景会比较频繁，这里使用LinkedList会更好
    private static List<String> realNodes = new LinkedList<>() ;
    // 虚拟节点，key表示虚拟节点的hash值，value表示虚拟节点的名称
    private static SortedMap<Integer, String> virtualNodes = new TreeMap<>() ;
    // 虚拟节点的数目，这里写死，为了演示需要，一个真实节点对应五个虚拟节点
    private static final int VIRTUAL_NODES = 5 ;

    static {
        // 先把原始的服务器添加到真实节点列表中
        for (String server : servers)
            realNodes.add(server) ;

        // 再添加虚拟节点，遍历LinkedList使用foreach循环效率会比较高
        for (String str : realNodes) {
            for (int i = 0; i < VIRTUAL_NODES; i++) {
                String virtualNodeName = str + "&&VN" + String.valueOf(i) ;
                int hash = getHash(virtualNodeName) ;
                System.out.println("虚拟节点[" + virtualNodeName + "]被添加, hash值为" + hash) ;
                virtualNodes.put(hash, virtualNodeName) ;
            }
        }
        System.out.println();
    }

    // 使用FNV1_32_HASH算法计算服务器的Hash值，这里不使用重新HashCode的方法，最终效果没区别
    private static int getHash(String str) {
        final int p = 16777619 ;
        int hash = (int) 2166136261L ;

        for (int i = 0; i < str.length(); i++)
            hash = (hash ^ str.charAt(i)) * p ;

        hash += hash << 13 ;
        hash ^= hash >> 7 ;
        hash += hash << 3 ;
        hash ^= hash >> 17 ;
        hash += hash<< 5 ;

        // 如果算出来的值为负数，则取其绝对值
        if (hash < 0)
            hash = Math.abs(hash) ;

        return hash ;
    }

    // 得到应当路由到的节点
    private static String getServer(String key) {
        // 得到该key的Hash
        int hash = getHash(key) ;
        // 得到大于该Hash值的所有Mao
        SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash) ;
        String virtualNode ;

        if(subMap.isEmpty()) {
            // 如果没有比该key的Hash值大的，则从第一个node开始
            Integer i = virtualNodes.firstKey() ;
            // 返回对应的服务器
            virtualNode = virtualNodes.get(i) ;
        }else {
            // 第一个key就是顺时针过去离node最近的那个节点
            Integer i = subMap.firstKey() ;
            // 返回对应的服务器
            virtualNode = subMap.get(i) ;
        }

        // virtualNode虚拟节点名称要截取一下
        if(virtualNode != null && !"".equals(virtualNode)){
            return virtualNode.substring(0, virtualNode.indexOf("&&VN")) ;
        }

        return null ;
    }

    public static void main(String[] args){
        String[] keys = {"太阳", "月亮", "星星", "宇宙"};
        for(int i=0; i<keys.length; i++){
            System.out.println("[" + keys[i] + "]的hash值为" +
                    getHash(keys[i]) + ", 被路由到结点[" + getServer(keys[i]) + "]");
        }
    }
}
